1. Field of the Invention
This invention relates to the field of data processing systems. More particularly, this invention relates to the control of branch target caches within data processing systems.
2. Description of the Prior Art
It is known within computer programs to incorporate branch instructions which redirect program flow from one point to another point. When such programs are executed in systems which prefetch program instructions it is desirable to redirect the prefetching activity to the branch target rapidly in order that there should not be an underflow in the program instructions available to be fed to the remaining parts of the data processing system for execution. However, it takes a finite amount of time to identify a branch instruction that has been fetched and determine whether or not it will actually be executed within the pipeline system. This tends to introduce a pipeline “bubble” where the latency associated with accessing the program instructions from memory will delay the return of the first instructions from the target address of the branch for a certain period during which no program instructions will be available to be fed to the rest of the data processing system. In some data processing systems an instruction queue is employed between the prefetching mechanism and the remainder of the data processing system to provide a small buffer of program instructions to be executed.
An additional mechanism that is known is the use of branch target address caches (BTACs) and branch target instruction caches (BTICs). A BTAC operates by detecting that a program instruction is being fetched from an address where a branch instruction was previously encountered and for which a branch target address of the previously encountered branch instruction has been stored. The BTAC can issue this cached target address to the prefetch unit to redirect program fetching to that target address working on the presumption that the branch instruction previously encountered will be present again and will act to redirect program flow to the same point executed.
The BTIC mechanism is similar except a sequence of program instructions starting from the target address of a previously encountered branch instruction is stored within the cache and available to be issued into the instruction queue and pipeline when the branch instruction previously encountered again. Caching the instructions at the branch target in this way enables them to be rapidly made available for issue to the instruction pipeline and avoid “bubbles” introduced by the latency of the memory system from which program instructions from the new location must be fetched.
Whilst the BTAC and BTIC approaches have many advantages, they do have the disadvantage of consuming relatively large number of gates in their implementation. These gates in turn consume electrical power in a disadvantages manor. Thus, the provision of BTAC and BTIC capabilities represents and overhead in terms of cost, complexity, power consumption and the like which must be balanced against the advantages which they provide.